#include "cache.h"
#include <vector>
#include <iostream>
#include <cstdio>
#include <cassert>

using namespace std;

typedef unsigned int uint;

std::vector<uint> masks;

#define BIT(x, lo, n) (((x) >> (lo)) & masks[(n)])

Cache::Cache(int C, int B, int S, int WP, int V, bool verbose)
  : C_(C), B_(B), S_(S), WP_(WP), V_(V), verbose_(verbose),
  tagSize_(32-C+S), idxSize_(C-B-S), ofsSize_(B),
  n_set_(1 << idxSize_), n_block_(1 << S), n_byte_(1 << B),
  sets_(n_set_, Set(n_block_, tagSize_, idxSize_, ofsSize_)),
  vc_(V >= 0 ? new Cache(B+V,B,V,WP,-1,verbose) : NULL),
  n_access_(0), n_time_(0),
  n_read_(0), n_readmiss_(0), n_readmissall_(0),
  n_write_(0), n_writemiss_(0), n_writemissall_(0),
  n_mem_(0), n_writeback_(0)
{
  masks.push_back(0);
  for (int i = 1; i < 32; i++) masks.push_back(masks[i-1]*2+1);   // prepare the bit masks
  if (verbose_) cout << (vc_ ? "dCache" : "vCache") << " parameters:\n";
  if (verbose_) cout << "C = " << C << " B = " << B << " S = " << S << " WP = " << (WP_ == WTNA?"WTNA":"WBWA") << " V = " << V_ << "\n";
  if (verbose_) cout << "n_set = " << n_set_ << " n_block_ = " << n_block_ << "\n";
}

Cache::~Cache(void)
{
  if (vc_) delete vc_;
}

void Cache::access(char rw, uint addr) 
{
  n_access_++;
  isRead_ = rw == 'r';
  split(addr);

  if (verbose_) cout << std::dec << n_access_ << "|Got " << rw << std::hex << " " << addr
       << "|tag = 0x" << tag_ 
       << "|index = " << std::dec << idx_;

  n_read_  += ( isRead_? 1:0);
  n_write_ += (!isRead_? 1:0);
  if (isHit())                                    // branching based on hit
    doHit();
  else if (vc_->isHit())                          // vc hit
    doVCHit();
  else                                            // or miss both caches
    doMiss();

  if (verbose_) cout << "|\n"; if (verbose_) cout.flush();
}

void Cache::split(uint addr)
{
  addr_ = addr;                                       // split the address into
  tag_ = BIT(addr_, idxSize_+ofsSize_, tagSize_);     // tag
  idx_ = BIT(addr_, ofsSize_, idxSize_);              // index
  ofs_ = BIT(addr_, 0, ofsSize_);                     // offset
  assert(addr_ == ((tag_ << (idxSize_+ofsSize_)) + (idx_ << ofsSize_) + ofs_));
  if (vc_) vc_->split(addr);
}

// ==============  SET    =================

Set::Set(unsigned int n_block, int tagSize, int idxSize, int ofsSize)
  : tagSize_(tagSize), idxSize_(idxSize), ofsSize_(ofsSize),
  blocks_(n_block, Block(tagSize, idxSize, ofsSize)),
  earlier_(blocks_), tags_(earlier_)
{
  for (uint i = 0; i < n_block; i++)         // at beginning every block is unused
    unused_.push(i);
}

Set::Set(const Set& s) 
  : tagSize_(s.tagSize_), idxSize_(s.idxSize_), ofsSize_(s.ofsSize_),
  blocks_(s.blocks_), earlier_(blocks_), tags_(earlier_)
{
  for (uint i = 0; i < blocks_.size(); i++)
    unused_.push(i);
}

int Set::find(uint tag)
{
  if (tags_.contains(tag))                   // find tag using the
    return tags_[tag];                       // mapped priority queue
  else                                       // complexity O(log n)
    return -1;
}

int Set::findLRU(void)
{
  int b = -1;
  if (!unused_.empty()) {                    // if there is unused block
    b = unused_.front();                     // use it
    unused_.pop();
  }
  else                                       // otherwise, use the priority queue
    b = tags_.min();                         // to find LRU block, complexity O(1)
  return b;
}

void Set::setBlock(int block, const Block& b)
{
  assert(block >= 0 && (uint) block < blocks_.size());
  assert(!blocks_[block].valid);
  assert(b.valid);
  blocks_[block].copy(b);                    // copy the block
  tags_.push(blocks_[block].tag, block);     // and update tag store
}


void Set::removeBlock(int block)
{
  assert(block >= 0 && (uint)block < blocks_.size());
  assert(blocks_[block].valid);
  blocks_[block].valid = false;              // invalidate the block
  tags_.remove(blocks_[block].tag);          // and remove from tag store
}


void Set::replaceBlock(int block, const Block& b)
{
  assert(block >= 0 && (uint) block < blocks_.size());
  assert(blocks_[block].valid);
  blocks_[block].copy(b);                    // replace with new block
  tags_.replace(blocks_[block].tag, block);  // also replace in tag store
}

// ==============  BLOCK  =================

Block::Block(int tagSize, int idxSize, int ofsSize)
  : tagSize_(tagSize), idxSize_(idxSize), ofsSize_(ofsSize),
  valid(false), dirty(false), tag(0), idx(0), time(0)
{
}


void Block::copy(const Block& b)
{
  uint addr = b.addr();                         // copy block
  tag = BIT(addr, idxSize_+ofsSize_, tagSize_); // take care of different tag and
  idx = BIT(addr, ofsSize_, idxSize_);          // index length
  dirty = b.dirty;
  valid = b.valid;
  time = b.time;
}


uint Block::addr(void) const
{
  return (tag << (idxSize_+ofsSize_)) + (idx << ofsSize_);
}


void Block::setAll(bool valid, bool dirty, unsigned int tag, unsigned int idx, unsigned int time)
{
  this->valid = valid;
  this->dirty = dirty;
  this->tag = tag;
  this->idx = idx;
  this->time = time;
}

// ==============  CACHE  =================

bool Cache::isHit(void)
{
  set_ = (C_ == B_+S_ ? 0 : idx_);           // set active set
  block_ = currentSet().find(tag_);          // find the tag
  return block_ >= 0;
}


void Cache::doHit(void)
{
  if (verbose_) cout << "|-dHits-";
  Block dBlk = currentBlock();               // get active block
  dBlk.time = n_time_++;                     // update access time
  if (!isRead_ && WP_ == WBWA)               // dirty if write-back
    dBlk.dirty = true;
  currentSet().replaceBlock(block_, dBlk);   // replace block
  if (!isRead_ && WP_ == WTNA) {
    n_mem_ += 4;                             // write through to memory
    if (verbose_) cout << "|Write through";
  }
}


void Cache::doMiss(void)
{
  if (verbose_) cout << "|-dMiss-|-vMiss-";

  if (!isRead_ && WP_ == WTNA) {
    n_mem_ += 4;
    if (verbose_) cout << "|Write through";          // write through
    return;
  }

  n_readmiss_     += ( isRead_? 1:0);
  n_writemiss_    += (!isRead_? 1:0);
  n_readmissall_  += ( isRead_? 1:0);
  n_writemissall_ += (!isRead_? 1:0);
  Block mBlk(tagSize_, idxSize_, ofsSize_);          // get the memory block
  mBlk.setAll(true, false, tag_, idx_, n_time_++);

  block_ = currentSet().findLRU();                   // find LRU block in dCache
  Block dBlk = currentBlock();
  if (dBlk.valid) {                                  // if dBlock is valid
    vc_->block_ = vc_->currentSet().findLRU();       // find LRU block in vCache
    Block vBlk = vc_->currentBlock();
    if (verbose_) cout << "|Evict dCache[" << std::dec << set_ << "][" << block_ << "] = " << std::hex << dBlk.tag
         << " to vCache[" << std::dec << vc_->set_ << "][" << vc_->block_ << "]";
    currentSet().removeBlock(block_);                // remove dBlock
    if (vBlk.valid) {                                // if vBlock is valid
      vc_->currentSet().removeBlock(vc_->block_);    // remove it from vCache
      if (verbose_) cout << "|Evict vCache[" << std::dec << vc_->set_ << "][" << vc_->block_ << "] = " << std::hex << vBlk.tag << " to memory";
      if (vBlk.dirty) {                              // if it is also dirty (write-back policy)
        n_mem_ += n_byte_;                           // then write-back
        n_writeback_ += n_byte_;
        if (verbose_) cout << "|Dirty vBlock|WB";
      }
      else if (WP_ == WBWA) {                        // otherwise, do nothing
        if (verbose_) cout << "|Clean vBlock|No WB";
      }
    }
    else
      if (verbose_) cout << "|Empty vBlock";
    dBlk.time = n_time_++;                           // update access time for dBlock
    vc_->currentSet().setBlock(vc_->block_, dBlk);   // write it to vCache
  }
  else {
    if (verbose_) cout << "|Empty dBlock";
  }
  sets_[set_].setBlock(block_, mBlk);                // write the memory block to dCache
  n_mem_ += n_byte_;
  if (verbose_) cout << "|Access memory";
}


void Cache::doVCHit(void)
{
  if (verbose_) cout << "|-dMiss-|-vHits-";
  Block vBlk = vc_->currentBlock();                  // get hit vBlock
  vBlk.time = n_time_++;                             // update access time
  vc_->currentSet().removeBlock(vc_->block_);
  if (!isRead_ && WP_ == WTNA) {                     // a write-through
    if (verbose_) cout << "|Write through";
    n_mem_ += 4;
    vc_->currentSet().setBlock(vc_->block_, vBlk);   // update it in vCache
  }
  else {
    n_readmiss_     += ( isRead_? 1:0);
    n_writemiss_    += (!isRead_? 1:0);
    block_ = currentSet().findLRU();                 // find LRU block in dCache
    Block dBlk = currentBlock();
    if (dBlk.valid) {                                // if dBlock is valid
      if (verbose_) cout << "|Evict dCache[" << std::dec << set_ << "][" << block_ << "] = " << std::hex << dBlk.tag
           << " to vCache[" << std::dec << vc_->set_ << "][" << vc_->block_ << "]";
      currentSet().removeBlock(block_);              // remove dBlock from dCache
      dBlk.time = n_time_++;                         // update access time
      vc_->currentSet().setBlock(vc_->block_, dBlk); // move dBlock to vCache
    }
    if (!isRead_)                                    // write-back policy ?
      vBlk.dirty = true;                             // set dirty
    if (verbose_) cout << "|Get block from vCache";
    currentSet().setBlock(block_, vBlk);             // move vBlock to dCache
  }
}

int Cache::size() const
{
  int n = n_set_ * n_block_;
  return n * (n_byte_*8 + 1 + tagSize_ + (WP_==WBWA?1:0));
}

void Cache::print_content(const char* name) const
{
  printf("%s content\n\n", name);
  for (unsigned int set = 0; set < n_set_; set++) {
    for (unsigned int block = 0; block < n_block_; block++) {
      printf("%s[%d][%d].tag = 0x%08x\t", name, set, block, sets_[set].blocks_[block].tag);
      printf("%s[%d][%d].time = %8u\t", name, set, block, sets_[set].blocks_[block].time);
      printf("%s[%d][%d].valid = %d\t", name, set, block, sets_[set].blocks_[block].valid ? 1 : 0);
      if (WP_ == WBWA)
        printf("%s[%d][%d].dirty = %d", name, set, block, sets_[set].blocks_[block].dirty ? 1 : 0);
      printf("\n");
    }
    printf("\n");
  }
  if (vc_) {
    printf("\n\n");
    vc_->print_content("vCache");
  }
}
